1. Field of the Invention
This invention relates generally to encoded data structure techniques and computer hardware, and more particularly to a coding method and computer hardware that supports bidirectional scanning of fields, which is economical in space, time and money.
2. Description of the Prior Art
In serial storage of data in a computer system a basic problem is that of identifying the type and/or length of unpredictable sequences of character-string data or fields. A fundamental requirement in connection with this problem is that the data sequence must be scannable in either direction.
There are two generally known prior art methods of encoding such sequences. One way is to reserve one or more "field separator" characters, which are not legal characters. (See E. H. Beitz, The Interpretation of Structured Stored Data Using Delimiters, Proc. 1970 ACM SIGFIDET Workshop on Data Description & Access, November, 1970, pp. 188-200). A cyclic FIFO buffer is utilized, in which a single pointer defines the current data entry point. Field names and/or lengths are stored adjacent to their value strings. FIG. 1 depicts such a prior art scheme wherein the field names and/or lengths A.sub.1, B.sub.1, C.sub.1 and D.sub.1 are stored adjacent to their respective value strings, Value (A).sub.1, (B).sub.1, (C).sub.1 and (D).sub.1. The letters L(A).sub.1, L(B).sub.1, L(C).sub.1 etc., refers to the lengths of the value fields respectively. To scan the buffer from left to right, the next field's starting address is computed by adding the preceding field's length and starting address. Unfortunately, however, with this technique right-to-left scan is not possible, because the value field is encountered first, and its name cannot be located without knowing its length, and vice versa.
Another prior art approach shown on FIG. 2 avoids this last restriction and permits random access to fields by segregating field names A.sub.2, B.sub.2, C.sub.2 and D.sub.2 from their value text Value(A).sub.2, Value(B).sub.2, Value(C).sub.2 etc. The field names are assumed to be fixed length and are kept in a separate ordered list, which can be indexed or scanned from either end. Before writing a tape block, the sequence of field names is appended to the value string sequence. FIG. 2 shows this solution, with field names A.sub.2, B.sub.2, C.sub.2 and D.sub.2 stored in reverse order from their value text Value (A).sub.2, (B).sub.2, (C).sub.2 etc., starting at the end of the data block. Names and values are accumulated simultaneously and both share a common pool of unused byte-cells in the middle of of the data block. However, this technique has the disadvantage of complicating physical concatenation of data and/or logical chaining.
One unique solution to the problem not believed to be in the prior art and still able to overcome one-directional scanning limitations is shown in FIG. 3A, wherein field names A.sub.3, B.sub.3, C.sub.3, D.sub.3 are embedded before and after each corresponding value string Value (A).sub.3, (B).sub.3, (C).sub.3, (D).sub.3 respectively. An obvious disadvantage with this technique, however, is that it doubles the space required to store the field names. What is needed is a technique which while overcoming one-directional scanning limitations, is at the same time economical in its use of space as well as of time and money.